package types;

import java.util.ArrayList;

public class helper_funcs {
	/* HELPERS */
	
	// prints the edges of the edge_list
	public static String print_edges (ArrayList<Edge> edge_list, int vertex)
	{
		String s = "vertex " + vertex + " has edges: { ";
		for(int i = 0; i < edge_list.size(); i++ )
		{
			s += edge_list.get(i).toString() + ", ";
		}

		s+= "}";
		System.out.println(s);
		return s;
	}
	
	//returns an edge array sorted in ascending order by edge weight
	//consider: rewriting in a more efficient manner
	public static void edge_sort (ArrayList<Edge>  list)
	{
		Edge temp;
		for (int i = 0; i < list.size(); i++)
		{
			for (int j = 0; j < list.size(); j++)
			{
				if(list.get(i).getWeight() < list.get(j).getWeight()) 
				{
					//System.out.println("changing order");
					temp = list.get(j);
					list.set(j, list.get(i));
					list.set(i, temp);
				}
			}
		}
		return;
	}

	// debug messages of printing edges
	public static void print_edges(ArrayList <Vertex> vertex_list){
		for(int i = 1; i < vertex_list.size(); i++)
		{
			System.out.println("Vertex: " + i + " has edges: " + vertex_list.get(i).edges.toString());
		}
	}
	
	// might get a problem with 1 as vertex as this is in terms of edges
	public static int sol_dist(Solution sol, int start)
	{
		int total_weight = 0;
		for(int i = start; i < sol.edges.size(); i++)
		{
			total_weight += sol.edges.get(i).getWeight();
		}
		return total_weight;
	}

	public static Solution return_min (ArrayList <Solution> solutions)
	{
		long distance = Long.MAX_VALUE ;
		long j;
		int track_min = 0;

		//System.out.println("");
		for(int i = 0; i < solutions.size(); i++)
		{
			if(solutions.get(i) != null)
			{
				j = solutions.get(i).sum;
				//System.out.println("comparing distances: " + distance + " vs " + j);
				if(distance > j)
				{
					distance = j;
					track_min = i;
				}
			}
		}

		if (distance == Integer.MAX_VALUE) {return null;}
		return solutions.get(track_min);
	}
	
	// returns the xth lowest edge that traverses to a vertex that hasn't been visited yet
	public static Edge find_low_edge(int vertex, int xth_lowest)
	{
		//System.out.println("location is " + Algorithms.location);
		int counter = -1;
		for (int i = 0; i < Main.vertex_list.get(vertex).edges.size(); i++)
		{
			if (  !Main.vertex_list.get( Main.vertex_list.get(vertex).edges.get(i).getDestination()).traversed  )
			{
				counter++;
				if (counter == xth_lowest)
				{
					return Main.vertex_list.get(vertex).edges.get(i);
				}
			}
		}
		System.out.println("no " + (xth_lowest + 1) + " edge available for vertex " + vertex);
		return null;
	}
	
	// sets edge valids to false and properly decrements Vertex valid count
	// only called before traversing
	// vertex is the vertex we are traversing to (going down a tree)
	public static void updateValidsTraversal (short vertex)
	{
		Main.vertex_list.get(vertex).traversed = true;
		for (int i = 0; i < Main.vertex_by_destination.get(vertex).edges.size(); i++)
		{
			// if the edge points to a vertex that hasn't been traversed to yet
			if(Main.vertex_by_destination.get(vertex).edges.get(i).valid)
			{
				//System.out.println("setting edge with source " +  
						//Main.vertex_by_destination.get(vertex).edges.get(i).getDestination() + " to invalid");
				
				Main.vertex_by_destination.get(vertex).edges.get(i).setValid(false);
				
				//System.out.println("decrementing valid count of " + Main.vertex_list.get(vertex).edges.get(i).getDestination()) ;
				Main.vertex_list.get(Main.vertex_list.get(vertex).edges.get(i).getDestination()).valid_count--;
			}
		}
	}
	
	// sets valid edges to true and properly increments vertex valid count
	// only called before returning
	// vertex is the vertex we are returning to (going up a tree)
	public static void updateValidsReturn (short vertex)
	{
		Main.vertex_list.get(vertex).traversed = false;
		for (int i = 0; i < Main.vertex_by_destination.get(vertex).edges.size(); i++)
		{
			// if the edge points to a vertex that hasn't been traversed to yet
			if(!Main.vertex_by_destination.get(vertex).edges.get(i).valid && 
					!Main.vertex_list.get(Main.vertex_list.get(vertex).edges.get(i).getDestination()).traversed)
			{
				//System.out.println("setting edge with source " +  
						//Main.vertex_by_destination.get(vertex).edges.get(i).getDestination() + " to valid");
				
				Main.vertex_by_destination.get(vertex).edges.get(i).setValid(true);
				
				//System.out.println("incrementing valid count of " + Main.vertex_list.get(vertex).edges.get(i).getDestination()) ;
				Main.vertex_list.get(Main.vertex_list.get(vertex).edges.get(i).getDestination()).valid_count++;
			}
		}
		
		for (int i = 0; i < Main.vertex_list.get(vertex).edges.size(); i++)
		{
			// if the edge points to a vertex that hasn't been traversed to yet
			if(!Main.vertex_list.get(vertex).edges.get(i).valid && 
					!Main.vertex_list.get((Main.vertex_list.get(vertex).edges.get(i).getDestination())).traversed)
			{
				//System.out.println("setting edge with source " +  
						//Main.vertex_by_destination.get(vertex).edges.get(i).getDestination() + " to valid");
				
				Main.vertex_list.get(vertex).edges.get(i).setValid(true);
				
				//System.out.println("incrementing valid count of " + Main.vertex_list.get(vertex).edges.get(i).getDestination()) ;
				Main.vertex_list.get(vertex).valid_count++;
			}
		}
		
	}
	
	// finds the vertex to make a manually created edge
	public static short find_vertex()
	{
		short vertex = 0;
		short count = Short.MAX_VALUE;
		
		//print_valids();
		
		for(int i = 1; i < Main.vertex_list.size(); i++)
		{
			if (count > Main.vertex_list.get(i).valid_count && !Main.vertex_list.get(i).traversed)
			{
				vertex = (short) i;
				count = Main.vertex_list.get(i).valid_count;
			}
		}
		return vertex;
	}
	
	// logic that happens during recursive implementation when traversing
	public static void recurse (short num)
	{
		Algorithms.location = Algorithms.location_tracker.get(Algorithms.location_tracker.size()-1);
		//System.out.println("at location " + Algorithms.location_tracker.get(Algorithms.location_tracker.size()-1) + ", valid count is " + 
				//Main.vertex_list.get(Algorithms.location_tracker.get(Algorithms.location_tracker.size()-1)).valid_count);
		// generate a new Edge
		Edge e;
		if (Main.vertex_list.get(Algorithms.location_tracker.get(Algorithms.location_tracker.size()-1)).valid_count <= num)
		{
			e = new Edge(Algorithms.location, find_vertex(), Main.max_weight);
		}
		else { e = find_low_edge(Algorithms.location, num); }
		
		Algorithms.solution.edges.add(e);
		Algorithms.location = e.getDestination();
		Algorithms.location_tracker.add(Algorithms.location);
		updateValidsTraversal(Algorithms.location);
		
		//System.out.println("traversing to " + Algorithms.location);
		
	}
	
	// resets valids to the point when branching ends
	public static void resetValids ()
	{
		// resets everything
		for (short i = 1; i < Main.vertex_list.size(); i++)
		{
			Main.vertex_list.get(i).traversed = false;
			Main.vertex_list.get(i).valid_count = (short) Main.vertex_list.get(i).edges.size();
			for (short j = 0; j < Main.vertex_list.get(i).edges.size(); j ++)
			{
				Main.vertex_list.get(i).edges.get(j).valid = true;
			}
		}
		
		// goes through remaining bit of location tracker and sets traversing again
		for (short i = 0; i < Main.branching; i ++)
		{
			updateValidsTraversal(Algorithms.location_tracker.get(i));
		}
	}
	
	public static void print_valids()
	{
		for(int k = 1; k < Main.vertex_list.size(); k++)
		{
			System.out.println("vertex " + k + " has " + Main.vertex_list.get(k).valid_count + " valids");
		}
	}

	public static void print_solution()
	{
		for (int i = 1; i < Algorithms.solution.edges.size(); i++)
		{
			System.err.println(Algorithms.solution.edges.get(i).toString());
		}
	}
	
	// sorts the solution so that it can be used as an adjacency list
	public static Solution sort_for_2_opt(Solution solution)
	{
		Solution temp = new Solution();
		temp.edges.ensureCapacity(solution.edges.size()+2);
		
		temp.sum = solution.sum;
		for( int i = 0; i < solution.edges.size()+2; i++ )
		{
			temp.edges.add(new Edge((short) i, (short) -1, 0));
		}

		for( int i = 0; i < solution.edges.size(); i++ )
		{
			temp.edges.set(solution.edges.get(i).getSource(), solution.edges.get(i));
		}	
		
		for (int i = 1; i < solution.edges.size()+1; i++ )
		{
			if (temp.edges.get(i).getDestination() == -1)
			{
				if (Main.vertex_hash.containsKey(temp.edges.get(i).getSource() + "," + 1))
				{
		//			System.out.println("there is an edge that goes to 1");
					temp.edges.set(i, Main.vertex_hash.get(temp.edges.get(i).getSource() + "," + 1));
				}
				else
				{
	//				System.out.println("there is not an edge that goes to 1, creating a penalty edge at location " + i);
					temp.edges.set(i, new Edge(temp.edges.get(i).getSource(), (short) 1, Main.max_weight));
				}
			}
		}
		
		
		return temp;
	}
	
	public static void updateSolution(short A, short B, short C, short D, Edge A_C, Edge B_D)
	{
		boolean A_before_C = true;
		short next = 1;
		short prev;
		short temp_loc;
		
		for(int i = 1; i < Algorithms.solution.edges.size(); i++)
		{
			if(A == next) { 
				A_before_C = true;
				break; }
			if(C == next) {
				A_before_C = false;
				break;
			}
			next = Algorithms.solution.edges.get(next).getDestination();
		}
		
		//System.out.println("A before C?.. " + A_before_C);
		if(A_before_C)
		{
			//print_solution();
			if(Main.vertex_hash.get(A+","+C) == null) 
			{ Algorithms.solution.edges.set(A, new Edge(A, C, Main.max_weight)); }
			else{
			Algorithms.solution.edges.set(A, Main.vertex_hash.get(A+","+C));}
			
			next = Algorithms.solution.edges.get(B).getDestination();
			prev = B;
			
			// forward trace from D to B, switching edge directions
			while (next != D)
			{
				//System.out.println("setting prev- " + Main.vertex_hash.get(next+","+ prev).toString() + " to slot " + next);
				temp_loc = Algorithms.solution.edges.get(next).getDestination();
				if(Main.vertex_hash.get(next+","+ prev) == null) 
				{ Algorithms.solution.edges.set(next, new Edge(next, prev, Main.max_weight)); }
				else {
				Algorithms.solution.edges.set(next, Main.vertex_hash.get(next+","+ prev)); }
				//System.out.println("setting slot " + next + " to " + Algorithms.solution.edges.get(next).toString());
				prev = next;
				next = temp_loc;		
			}
			
			if(Main.vertex_hash.get(B+","+ D) == null) 
			{ Algorithms.solution.edges.set(B, new Edge(B, D, Main.max_weight)); }
			else {
			Algorithms.solution.edges.set(B, Main.vertex_hash.get(B+","+D)); }
			
		}
		
		else
		{
			if(Main.vertex_hash.get(C+","+ A) == null) 
			{ Algorithms.solution.edges.set(C, new Edge(C, A, Main.max_weight)); }
			else {
			Algorithms.solution.edges.set(C, Main.vertex_hash.get(C+","+A)); }
			
			next = Algorithms.solution.edges.get(D).getDestination();
			prev = D;
			// forward trace from D to B, switching edge directions
			while (next != B)
			{
				//System.out.println("setting prev- " + Main.vertex_hash.get(next+","+ prev).toString() + " to slot " + next);
				temp_loc = Algorithms.solution.edges.get(next).getDestination();
				if(Main.vertex_hash.get(next+","+ prev) == null) 
				{ Algorithms.solution.edges.set(next, new Edge(next, prev, Main.max_weight)); }
				else {
				Algorithms.solution.edges.set(next, Main.vertex_hash.get(next+","+prev)); }
				prev = next;
				next = temp_loc;		
			}
			if(Main.vertex_hash.get(next+","+ prev) == null) 
			{ Algorithms.solution.edges.set(D, new Edge(D, B, Main.max_weight)); }
			else {
			Algorithms.solution.edges.set(D, Main.vertex_hash.get(D+","+B)); }
			
		}
		
	}
	
	public static void removeAndUpdate() {
		Algorithms.solution.edges.remove(Algorithms.solution.edges.size()-1);
		Algorithms.location_tracker.remove(Algorithms.location_tracker.size()-1);
		updateValidsReturn(Algorithms.location);
	}
	
	public static void findNullValue()
	{
		for(int i = 0; i < Algorithms.solution.edges.size(); i++)
		{
			if (Algorithms.solution.edges.get(i) == null)
			{
				System.err.println("slot " + i + " is null...");
			}
			else if ( Algorithms.solution.edges.get(i).getSource() == 0)
			{
				System.err.println("warning, edge at solution spot " + i + " has a source of 0");
				System.err.println(Algorithms.solution.edges.get(i).toString());
			}
			else if ( Algorithms.solution.edges.get(i).getDestination() == 0)
			{
				System.err.println("warning, edge at solution spot " + i + " has a destination of 0");
				System.err.println(Algorithms.solution.edges.get(i).toString());
			}
			else {
			if ( Algorithms.solution.edges.get(i).getWeight() == 0)
			{
				System.err.println("warning, edge at solution spot " + i + " has a weight of 0");
				System.err.println(Algorithms.solution.edges.get(i).toString());
			}
			}
			
		}
	}
	
	public static void store_penalty_edges()
	{
		Main.penalty_edges.clear();
		for (int i = 2; i < Main.solution.edges.size()-1; i++)
		{
			if(Main.solution.edges.get(i).getWeight() == Main.max_weight) 
			{
				Main.penalty_edges.add(Main.solution.edges.get(i));
			}
		}
		
		int size = Main.penalty_edges.size();
		for (int i = 0; i < size; i++)
		{
			if(Main.penalty_edges.get(i).getDestination() < 2 || Main.penalty_edges.get(i).getSource() < 2)
			{
				Main.penalty_edges.remove(i);
				i--;
				size--;
			}
		}
	}
	
	public static void find_shitty_edges()
	{
		Main.bad_edges.clear();
		Main.bad_edges = new ArrayList <Edge> ();
		Main.bad_edges.ensureCapacity(Main.solution.edges.size()/30);
		
		int lowest_weight = 0;
		int capacity = 0;
		int max_capacity = Main.solution.edges.size()/30;
		
		for (int i = 2; i < Main.solution.edges.size()-1; i++)
		{
			if (capacity != max_capacity)
			{
				if (lowest_weight > Main.solution.edges.get(i).getWeight())
				{
					lowest_weight = Main.solution.edges.get(i).getWeight();
				}
			}
			else if (Main.solution.edges.get(i).getWeight() > lowest_weight) 
			{
				for (int j = 0; j < max_capacity; j++)
				{
					Edge temp =  Main.bad_edges.get(j);
					if (temp.getWeight() < lowest_weight)
					{
						Main.bad_edges.set(j, Main.solution.edges.get(i));
						lowest_weight = Main.solution.edges.get(i).getWeight();
					}
				}
			}
		}
		
		
		int size = Main.bad_edges.size();
		for (int i = 0; i < size; i++)
		{
			if(Main.bad_edges.get(i).getDestination() < 2 || Main.bad_edges.get(i).getSource() < 2)
			{
				Main.bad_edges.remove(i);
				i--;
				size--;
			}
		}
		
	}
	
}
